package zuochengyun.chapter8;

//不包含本位置值的累成数组       P380
//不能使用除法
public class ProductExceptSelf {

	public int[] product2(int[] arr){
		if(arr == null || arr.length < 2){
			return null;
		}
		//方法就是生成两个长度和arr一样的数组left和right
		//分别表示从左到右的累乘以及从右到左的累乘
		//这样res[i] = left[i - 1] * right[i + 1]
		//至于res[0] = right[1], res[length - 1] = left[length - 2]
 		//但是为了避免两个数组的开销，我们可以使用res来暂存left，然后用变量从右往左遍历的时候来记录right
		int[] res = new int[arr.length];
		res[0] = arr[0];
		for (int i = 1; i < res.length; i++) {
			res[i] = res[i - 1] * arr[i];
		}
		
		int temp = 1;  //这个用来替代right数组
		for (int i = arr.length - 1; i > 0; i--) {
			res[i] = res[i - 1] * temp;
			temp *= arr[i]; 
		}
		res[0] = temp;
		return res;
	}
}
